package practice;

/**
 * LCR 170. 交易逆序对的总数（困难）
 */

public class T1 {

    public static int reversePairs(int[] record){
        if (record == null || record.length < 2) return 0;
        return process(record,0,record.length - 1);
    }

    private static int process(int[] arr, int l, int r) {
        if (l == r) return 0;
        int mid = l + ((r - l) >> 1);
        return process(arr,l,mid) + process(arr,mid + 1,r) + merge(arr,l,mid,r);
    }

    private static int merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        int res = 0;//记录逆序数的个数
        while (p1 <= mid && p2 <= r){
            res += arr[p1] > arr[p2] ? (r - p2 + 1) : 0;
            help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];//由大到小排序
        }
        while (p1 <= mid) help[i++] = arr[p1++];
        while (p2 <= r) help[i++] = arr[p2++];
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {9, 7, 5, 4, 6};
        System.out.println(reversePairs(arr));
    }
}
